package main

func main() {
	rooms1 := [][]int {{1},{2},{3},{}}
	canVisitAllRooms(rooms1)
}

// 深度优先
var (
	num int
	vis []bool
)

func canVisitAllRooms(rooms [][]int) bool {
	n := len(rooms)
	num = 0
	vis = make([]bool, n)
	dfs(rooms, 0)
	return num == n
}

func dfs(rooms [][]int, x int) {
	vis[x] = true
	num++
	for _, it := range rooms[x] {
		if !vis[it] {
			dfs(rooms, it)
		}
	}
}


// 广度优先


func canVisitAllRooms1(rooms [][]int) bool {
	n := len(rooms)
	num := 0
	vis := make([]bool, n)
	queue := []int{}
	vis[0] = true
	queue = append(queue, 0)
	for i := 0; i < len(queue); i++ {
		x := queue[i]
		num++
		for _, it := range rooms[x] {
			if !vis[it] {
				vis[it] = true
				queue = append(queue, it)
			}
		}
	}
	return num == n
}

